package _2022.hot100._10_正则式匹配;

/**
 * @author： YHSimon
 * @date： 2022-03-30 14:33
 */
public class Solution {


    //动态规划
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }


    //报错
    public boolean isMatch2(String s,String p){
        int pLen=p.length();
        int i=0,j=0;
        //pre存储p中上一个字符
        char pre=p.charAt(0);
        while (j<pLen){
            char c=p.charAt(j);
            if(97<=c&&c<=122){
                pre=c;
                if(c==s.charAt(i)){
                    i++;
                    j++;
                }else{
                    return false;
                }
            }else{
                if (c=='.'){
                    i++;
                    j++;
                    pre=c;
                }else if(c=='*'){
                    if(pre!='.'){
                        while(i<s.length()&&s.charAt(i)==pre){
                            i++;
                        }
                        j++;
                    }else{
                        char tmp=s.charAt(i);
                        while(i<s.length()&&s.charAt(i)==tmp){
                            i++;
                            pre=tmp;
                        }
                        j++;
                    }

                }
            }
        }

        return i>=s.length();
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isMatch("ab", ".*c"));
    }
}
